package leetcode_zh

import "math"

/**
 * @Description: 1. 两数之和 简单
 * @Keyword: 借助额外存储
 * @Author: kami
 * @Date: 2022/6/27 15:54
 **/
func twoSum1(nums []int, target int) []int {
	var seenMap = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if idx, ok := seenMap[nums[i]]; ok {
			return []int{idx, i}
		}
		seenMap[target-nums[i]] = i
	}
	return []int{}
}

/**
 * @Description: 2. 两数相加
 * @Keyword: 逆序链表，进位
 * @Author: kami
 * @Date: 2022/6/27 15:57
 **/
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
	var dumyHead = new(ListNode)
	var curRes = dumyHead
	var curL1 = l1
	var curL2 = l2
	var take int
	for curL1 != nil || curL2 != nil {
		var curVal int
		if curL1 != nil && curL2 != nil {
			curVal = curL1.Val + curL2.Val
			curL1 = curL1.Next
			curL2 = curL2.Next
		} else if curL1 != nil {
			curVal = curL1.Val
			curL1 = curL1.Next
		} else {
			curVal = curL2.Val
			curL2 = curL2.Next
		}
		if take > 0 {
			curVal += take
		}
		take = curVal / 10
		mod := curVal % 10
		curRes.Next = &ListNode{
			Val: mod,
		}
		curRes = curRes.Next
	}
	if take > 0 {
		curRes.Next = &ListNode{
			Val: take,
		}
	}

	return dumyHead.Next
}

/**
 * @Description: 3. 无重复字符的最长子串 中等
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/6/27 16:08
 **/
func lengthOfLongestSubstring3(s string) int {
	// 字符：下标
	var seen = make(map[byte]int)
	var startIdx int
	var maxCnt int
	for i := 0; i < len(s); i++ {
		if idx, ok := seen[s[i]]; ok {
			// 窗口左侧
			if idx < startIdx {
				var diff = i - startIdx + 1
				if diff > maxCnt {
					maxCnt = diff
				}
			} else {
				// 窗口内
				startIdx = idx + 1
			}
		} else {
			var diff = i - startIdx + 1
			if diff > maxCnt {
				maxCnt = diff
			}
		}
		seen[s[i]] = i
	}
	return maxCnt
}

/**
 * @Description: 4. 寻找两个正序数组的中位数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/27 17:04
 **/
func findMedianSortedArrays4(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}

	var m = len(nums1)
	var n = len(nums2)
	var totalCnt = m + n
	var totalLeft = (totalCnt + 1) / 2
	// 確定分割线，第一个数组的分割线
	var left int

	for left <= m {
		var nums1Right int
		if left == m {
			// 分割线在第一个数组的最右侧
			nums1Right = math.MaxInt
		} else {
			nums1Right = nums1[left]
		}

		var nums2Left int
		if totalLeft == left {
			// 分割线在第一个数组的最右侧，第二个数组的最左侧
			nums2Left = math.MinInt
		} else {
			nums2Left = nums2[totalLeft-left-1]
		}

		if nums2Left > nums1Right {
			left++
		} else {
			break
		}
	}
	var nums1Left = math.MinInt
	if left > 0 {
		nums1Left = nums1[left-1]
	}
	var nums1Right = math.MaxInt
	if left != m {
		nums1Right = nums1[left]
	}
	var num2Left = math.MinInt
	if totalLeft != left {
		num2Left = nums2[totalLeft-left-1]
	}
	var num2Right = math.MaxInt
	if totalLeft-left != n {
		num2Right = nums2[totalLeft-left]
	}

	if totalCnt%2 == 0 {
		return float64(getMax(nums1Left, num2Left)+getMin(nums1Right, num2Right)) / 2.0
	} else {
		return float64(getMax(nums1Left, num2Left))
	}
}

/**
 * @Description: 5. 最长回文子串 中等
 * @Keyword: 中心扩展算法
 * @Author: kami
 * @Date: 2022/6/27 19:26
 **/
func longestPalindrome5(s string) string {
	if s == "" {
		return ""
	}
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		left1, right1 := expandAroundCenter(s, i, i)
		left2, right2 := expandAroundCenter(s, i, i+1)
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
	}
	return left + 1, right - 1
}

/**
 * @Description: 6. Z 字形变换 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 9:57
 **/
func convert6(s string, numRows int) string {
	if numRows < 2 {
		return s
	}
	var rows = make([][]byte, numRows)
	var idx = 0
	var flag = -1
	for i := 0; i < len(s); i++ {
		rows[idx] = append(rows[idx], s[i])
		if idx == 0 || idx == numRows-1 {
			flag = -flag
		}
		idx += flag
	}
	var res string
	for i := 0; i < numRows; i++ {
		res += string(rows[i])
	}
	return res
}

/**
 * @Description: 7. 整数反转 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 10:47
 **/
func reverse7(x int) int {
	var isNegetive bool
	if x < 0 {
		isNegetive = true
		x = -x
	}
	var maxBytes = "2147483647"

	for x%10 == 0 && x/10 > 0 {
		x = x / 10
	}
	var reverseX []uint8
	var res int
	for x > 0 {
		reverseX = append(reverseX, uint8(x%10))
		x = x / 10
	}

	if len(reverseX) == len(maxBytes) {
		for i := 0; i < len(reverseX); i++ {
			if reverseX[i] < (maxBytes[i] - '0') {
				break
			}
			if reverseX[i] > (maxBytes[i] - '0') {
				return 0
			}
		}
	}
	res = convertToIntNum(reverseX)
	if isNegetive {
		return -res
	}
	return res
}

func convertToIntNum(nums []uint8) int {
	var res int
	for i := 0; i < len(nums); i++ {
		res = res*10 + int(nums[i])
	}
	return res
}

/**
 * @Description: 8. 字符串转换整数 (atoi) 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/29 11:38
 **/
func myAtoi8(s string) int {
	if len(s) == 0 {
		return 0
	}

	var nums []byte
	var isNegetive bool
	for i := 0; i < len(s); i++ {
		if s[i] > '0' && s[i] <= '9' {
			nums = append(nums, s[i])
			if i > 0 && s[i-1] == '-' {
				isNegetive = true
			}
			i++
			for i < len(s) && s[i] >= '0' && s[i] <= '9' {
				nums = append(nums, s[i])
				i++
			}
			break
		}
		if (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || s[i] == '.' {
			return 0
		}
	}
	var maxBytes = "2147483647"
	if len(nums) > len(maxBytes) {
		if isNegetive {
			return math.MinInt32
		}
		return math.MinInt32
	}
	if len(nums) == len(maxBytes) {
		for i := 0; i < len(nums); i++ {
			if nums[i] < maxBytes[i] {
				break
			}
			if nums[i] > maxBytes[i] {
				if i == len(nums)-1 && isNegetive && nums[i] == '8' {
					return math.MinInt32
				}
				return math.MaxInt32
			}
		}
	}
	var res int
	for i := 0; i < len(nums); i++ {
		res = res*10 + int(nums[i]-'0')
	}
	if isNegetive {
		return -res
	}
	return res
}
